/**
 * https://leetcode.cn/problems/number-of-digit-one/submissions/572312937/
 * 233. 数字 1 的个数
 * medium 陈贝纯 2024.10.13
 * 数位dp
 */


class Solution {
public:
    int t;
    int l=0;
    int visit=0;
    int sum=0;
    void dfs(int num,int n){
        if(n>=l){
            if(num<=t)
                sum+=visit;
            return;
        }for(int i=0;i<10;++i){
            if(i==1){
                visit++;
                dfs(num*10+i,n+1);
                visit--;
            }else
                dfs(num*10+i,n+1);
        }
    }
    int countDigitOne(int n) {
        int j=n;
        t=n;
        while(j/10){
            l++;
            j/=10;
        }
        int current=1;
        for(int i=0;i<l;++i){
            sum+=(current+sum*9);
            current*=10;
        }
        if(l==9)
        return sum+1;
        if(j>=2)
        sum+=(current+sum*(j-1));
        if(j==1)
        visit++;
        dfs(j,0);
        return sum;
    }
};